package alg

import (
	"fmt"
	"math/rand"
	"time"
)

// 题目一：公司有n个组，每组人数相同，>=1人，需要进行随机的组队吃饭。
// 要求：1. 两两一队，不能落单，落单则三人一队
//   2. 一个人只出现一次
//   3. 队伍中至少包含两个组
//   4. 随机组队，重复执行程序得到的结果不一样
//
// 思路: 高端食材往往只需要最简单的烹饪
// 1. 先得出总数, 并平化为一维数组 O(n)
// 2. 计算出是奇数还是偶数, 命名为分数 O(1)
// 3. 根据分数进行 n个分组, 随机从数组中获取元素添加到分组, (兼容组不同人数，还有优化空间)不够n等分情况下最后一个分组元素的个数为 分数-m O(n)
//
// Result: T(n)=O(n+1+n)=O(n)
//
// First Run:
// 1. listCount=17, listConv=[张三1 张三2 张三3 张三4 张三5 王五1 王五2 王五2 赵四1 赵四2 赵四3 赵四4 马六1 马六2 马六3 马六4 马六5]
// 2. listCount=17, score=3
// 3. newGrouList=[[王五2 王五2 张三2] [马六5 王五1 马六1] [马六2 赵四1 赵四3] [赵四2 张三4 张三3] [马六4 张三5 张三1] [赵四4 马六3]]
//
// Second Run:
// 1. listCount=17, listConv=[张三1 张三2 张三3 张三4 张三5 王五1 王五2 王五2 赵四1 赵四2 赵四3 赵四4 马六1 马六2 马六3 马六4 马六5]
// 2. listCount=17, score=3
// 3. newGrouList=[[张三4 王五1 马六5] [张三3 张三5 马六1] [赵四4 马六3 王五2] [赵四1 张三2 马六2] [马六4 赵四3 王五2] [赵四2 张三1]]
func ArrGroup() {
	// 小组列表
	// groupList := [][]string{
	// 	{"张三1", "张三2", "张三3", "张三4", "张三5"},
	// 	{"王五1", "王五2", "王五2"},
	// 	{"赵四1", "赵四2", "赵四3", "赵四4"},
	// 	{"马六1", "马六2", "马六3", "马六4", "马六5"},
	// }
	groupList := [][]string{
		{"张三1", "张三2", "张三3", "张三4", "张三5"},
		{"王五1", "王五2", "王五2", "王五4", "王五5"},
		{"赵四1", "赵四2", "赵四3", "赵四4", "赵四5"},
		{"马六1", "马六2", "马六3", "马六4", "马六5"},
	}
	// groupList := [][]string{
	// 	{"张三1", "张三2", "张三3", "张三4", "张三5"},
	// 	{"王五1", "王五2", "王五2", "王五4", "王五5"},
	// 	{"赵四1", "赵四2", "赵四3", "赵四4", "赵四5"},
	// 	{"马六1", "马六2", "马六3", "马六4", "马六5"},
	// 	{"A1", "B2", "C3", "D4", "E5"},
	// }

	// 定义结果数据和临时数据变量
	listConv := []string{}
	newGrouList := [][]string{}
	listCount := 0
	score := 2

	// 1. 先得出总数, 并平化为一维数组 O(n)
	for _, v := range groupList {
		listCount += len(v)
		listConv = append(listConv, v[:]...)
	}
	fmt.Printf("1. listCount=%d, listConv=%+v \n", listCount, listConv)

	// 2. 计算出是奇数还是偶数, 命名为分数 O(1)
	if listCount%2 == 1 {
		score = 3
	}
	fmt.Printf("2. listCount=%d, score=%d \n", listCount, score)

	// 3. 根据分数进行 n个分组, 随机从数组中获取元素添加到分组, (兼容组不同人数，还有优化空间)不够n等分情况下最后一个分组元素的个数为 分数-m O(n)
	tempNum := 0
	tempList := []string{}
	tempCount := listCount
	// rand设置一个种子 纳秒
	rand.Seed(time.Now().UnixNano())
	for tempNum < score && tempCount > 0 {
		tempNum++
		// 随机数
		index := rand.Intn(tempCount)
		tempCount--

		// 添加到新的列表中
		tempList = append(tempList, listConv[index])

		// 删除已使用元素
		listConv = append(listConv[:index], listConv[index+1:]...)

		// 符合分组进行处理
		if tempNum == score || tempCount == 0 {
			newGrouList = append(newGrouList, tempList)
			tempList = []string{}
			tempNum = 0
			continue
		}
	}

	fmt.Printf("3. newGrouList=%+v \n", newGrouList)
}
